//
// Created by francklinson on 2021/7/25 AT 0:05.
//
#include <vector>
#include <iostream>
#include <unordered_map>
#include <unordered_set>

using namespace std;

class Solution {
public:
    vector<int> restoreArray(vector<vector<int>> &adjacentPairs) {
        unordered_map<int, vector<int>> edges;
        for (auto &pair:adjacentPairs) {
            edges[pair[0]].push_back(pair[1]);
            edges[pair[1]].push_back(pair[0]);
        }
        vector<int> ans;
        unordered_set<int> seen;
        int begin = 0;
        for (auto &edge:edges) {
            if (edge.second.size() == 1) {
                begin = edge.first;  // find the array beginning
                break;
            }
        }
        ans.push_back(begin);
        seen.insert(begin);
        for (int i = 0; i < adjacentPairs.size(); ++i) { // conduct the iteration
            for (auto &neighbor:edges[begin]) {
                if (!seen.count(neighbor)) {
                    ans.push_back(neighbor);
                    begin = neighbor;
                    seen.insert(neighbor);
                }
            }
        }
        return ans;

    }
};

class Solution2 { // 题解 不需要记录过程
public:
    vector<int> restoreArray(vector<vector<int>> &adjacentPairs) {
        unordered_map<int, vector<int>> mp;
        for (auto &adjacentPair : adjacentPairs) {
            mp[adjacentPair[0]].push_back(adjacentPair[1]);
            mp[adjacentPair[1]].push_back(adjacentPair[0]);
        }

        int n = adjacentPairs.size() + 1;
        vector<int> ret(n);
        for (auto &m : mp) {
            if (m.second.size() == 1) {
                ret[0] = m.first;
                break;
            }
        }

        ret[1] = mp[ret[0]][0];
        for (int i = 2; i < n; i++) {
            auto &adj = mp[ret[i - 1]];
            ret[i] = ret[i - 2] == adj[0] ? adj[1] : adj[0];
        }
        return ret;
    }
};


int main() {
    vector<vector<int>> adjacentPairs{{2, 1},
                                      {3, 4},
                                      {3, 2}};
    Solution2 solution;
    auto ans = solution.restoreArray(adjacentPairs);
    for (auto &x:ans) cout << x << endl;
    return 0;
}

